package com.leetcode.algorithm.y19.m03;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Queue;
import java.util.Stack;

import com.leetcode.algorithm.common.TreeNode;

/**
 * leetcode-cn.com
 * (done)199. 二叉树的右视图
 * (done)508. 出现次数最多的子树元素和
 * (done)998. 最大二叉树 II
 * @author: jie.deng
 * @time: 2019年3月26日 下午9:36:03
 */
public class MySolution0326 {
	
	/**
	 * 199. 二叉树的右视图
	 * 
     * 给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
     * 
     * 示例:
     * 
     * 输入: [1,2,3,null,5,null,4]
     * 输出: [1, 3, 4]
     * 解释:
     * 
     *    1            <---
     *  /   \
     * 2     3         <---
     *  \     \
     *   5     4       <---
	 * @param root
	 * @return
	 */
	public List<Integer> rightSideView(TreeNode root) {
		// 层次遍历
		List<Integer> list = new ArrayList<Integer>();
		if (root == null) {
			return list;
		}
		Queue<TreeNode> queue = new LinkedList<TreeNode>(); // 广度优先搜索，使用队列实现，先进先出
		queue.offer(root);
		while (!queue.isEmpty()) {
			int size = queue.size(); // 当前层次结点个数
			for (int i = 0; i < size; i++) {
				TreeNode node = queue.poll();
				if (i == 0) {
					list.add(node.val); // 遍历当前结点
				}
				if (node.right != null) {
					queue.offer(node.right);
				}
				if (node.left != null) {
					queue.offer(node.left);
				}
			}
		}
		return list;
	}
    
    /**
     * 508. 出现次数最多的子树元素和
     * 
     * 给出二叉树的根，找出出现次数最多的子树元素和。一个结点的子树元素和定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。然后求出出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的元素（不限顺序）。
     * 
     *  
     * 
     * 示例 1
     * 输入:
     * 
     *   5
     *  /  \
     * 2   -3
     * 返回 [2, -3, 4]，所有的值均只出现一次，以任意顺序返回所有值。
     * 
     * 示例 2
     * 输入:
     * 
     *   5
     *  /  \
     * 2   -5
     * 返回 [2]，只有 2 出现两次，-5 只出现 1 次。
     * 
     *  
     * 
     * 提示： 假设任意子树元素和均可以用 32 位有符号整数表示。
     * @param root
     * @return
     */
	public int[] findFrequentTreeSum(TreeNode root) {
		// 后续遍历
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		int maxCnt = 0;
		if (root == null) {
			return new int[] {};
		}
		TreeNode pre = null; // 划重点:记录上次遍历的结点
		Stack<TreeNode> stack = new Stack<TreeNode>();
		stack.push(root);
		while (!stack.isEmpty()) {
			TreeNode cur = stack.peek();
			if ((cur.left == null && cur.right == null)
					|| ((cur.right == null ? cur.left : cur.right) == pre)) {
				// 划重点:如果当前结点没有孩子或者上次遍历的结点为左孩子(没有右孩子的情况)或者右孩子，则遍历当前结点
				stack.pop();
				int sum = cur.val;
				if (cur.right != null) {
					sum += cur.right.val;
				}
				if (cur.left != null) {
					sum += cur.left.val;
				}
				int cnt = map.containsKey(sum) ? map.get(sum) + 1 : 1;
				if (cnt > maxCnt) {
					maxCnt = cnt;
				}
				map.put(sum, cnt);
				cur.val = sum;
				pre = cur;
			} else {
				if (cur.right != null) {
					stack.push(cur.right);
				}
				if (cur.left != null) {
					stack.push(cur.left);
				}
			}
		}
	
		List<Integer> list = new ArrayList<Integer>();
		for (Entry<Integer, Integer> entry : map.entrySet()) {
			if (entry.getValue() == maxCnt) {
				list.add(entry.getKey());
			}
		}
		Collections.sort(list);
		int[] ret = new int[list.size()];
		for (int i = 0; i < ret.length; i++) {
			ret[i] = list.get(i);
		}
		return ret;
	}
    
    /**
     * 998. 最大二叉树 II
     * 
     * 最大树定义：一个树，其中每个节点的值都大于其子树中的任何其他值。
     * 
     * 给出最大树的根节点 root。
     * 
     * 就像之前的问题那样，给定的树是从表 A（root = Construct(A)）递归地使用下述 Construct(A) 例程构造的：
     * 
     * 如果 A 为空，返回 null
     * 否则，令 A[i] 作为 A 的最大元素。创建一个值为 A[i] 的根节点 root
     * root 的左子树将被构建为 Construct([A[0], A[1], ..., A[i-1]])
     * root 的右子树将被构建为 Construct([A[i+1], A[i+2], ..., A[A.length - 1]])
     * 返回 root
     * 请注意，我们没有直接给定 A，只有一个根节点 root = Construct(A).
     * 
     * 假设 B 是 A 的副本，并附加值 val。保证 B 中的值是不同的。
     * 
     * 返回 Construct(B)。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 
     * 
     * 输入：root = [4,1,3,null,null,2], val = 5
     * 输出：[5,4,null,1,3,null,null,2]
     * 解释：A = [1,4,2,3], B = [1,4,2,3,5]
     * 示例 2：
     * 
     * 
     * 输入：root = [5,2,4,null,1], val = 3
     * 输出：[5,2,4,null,1,null,3]
     * 解释：A = [2,1,5,4], B = [2,1,5,4,3]
     * 示例 3：
     * 
     * 
     * 输入：root = [5,2,3,null,1], val = 4
     * 输出：[5,2,4,null,1,3]
     * 解释：A = [2,1,5,3], B = [2,1,5,3,4]
     *  
     * 
     * 提示：
     * 
     * 1 <= B.length <= 100
     * @param root
     * @param val
     * @return
     */
	public TreeNode insertIntoMaxTree(TreeNode root, int val) {
		TreeNode node = new TreeNode(val);
		if (root == null) {
			return node;
		}
		if (val > root.val) {
			node.left = root;
			return node;
		} else {
			root.right = insertIntoMaxTree(root.right, val);
		}
		return root;
	}
    
}
